#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size(), m = 0;
        for (auto i : stones) m += i;
        vector<bool> dp(m / 2 + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = m / 2; j > 0; j--)
                dp[j] = dp[j] || (j >= stones[i - 1] ? dp[j - stones[i - 1]] : 0);
        int ma = 0;
        for (int j = m / 2; j >= 0; j--)
            if (dp[j])
            {
                ma = j;
                break;
            }
        return m - 2 * ma;
    }
};